package leetcode.wtx;

import java.util.StringJoiner;

/**
 * 字符串匹配 z-algorithm
 * https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/
 */
public final class Zalgo {
    private static int updateLeftZbox(String targetString, int left, int right) {
      final int len = targetString.length();
      while(right < len && targetString.charAt(left) == targetString.charAt(right)) {
        ++left;
        ++right;
      }
      return right - 1;
    }
    /**
     * given `targetString`, we compute z-count for it
     * @param targetString
     * @return int[]
     */
    public static int[] getZcount(String targetString) {
      if (targetString == null ||
        targetString.length() == 0 ) {
          return null;
      }

      int[] z = new int[targetString.length()];
      int leftZbox = 1, rightZbox = 0;
      int[] zcount = new int[targetString.length()];
      zcount[0] = -1;
      rightZbox = updateLeftZbox(targetString, 0, 1);
      z[1] = rightZbox - leftZbox + 1;
      for (int i = 2; i < targetString.length(); ++i) {
        int k = i - leftZbox;
        
        if (z[k] < rightZbox - i + 1) {
          z[i] = z[k];
        } else {
          // update rightZbox
          if (rightZbox < i) {
            rightZbox = i;
          }
          rightZbox = updateLeftZbox(targetString, rightZbox - i, rightZbox);
          z[i] = rightZbox - i + 1;
          leftZbox = i;
        }
      }
      return z;
    }

    public static int[] twoFingerMethod(String targetString) {
      int[] zcount = new int[targetString.length()];
      for (int i = 1; i < targetString.length(); ++i) {
          zcount[i] = updateLeftZbox(targetString, 0, i) - i + 1;
      }
      return zcount; 
    }
    /**
     * Says hello to the world.
     * @param args The arguments of the program.
     */
    public static void main(String[] args) {
      String a = "cbbbaabbbccabccaaccbcaccbaaaaaababcb";
      int[] z = getZcount(a);
      StringJoiner sj = new StringJoiner(", ", "[", "]");
      for (int i : z) {
        sj.add(""+i);
      }
      System.out.println(sj.toString());
    }
}
